Description of the Related Art
Conventional systems may include storage configurations with Redundant Array of Independent Disks (RAID) devices. There are several levels of RAID devices. For example, RAID devices Level 5 (RAID-5 devices) store parity information using a rotating parity array.
Parity information is used to check whether data that has been moved from one storage area to another storage area (e.g., within a storage device) or that has been transmitted between two components (e.g., two computers or two storage devices) has been lost or written over. In particular, an additional binary digit, the parity bit, is added to a group of bits that are moved together. Before the group of bits are sent, the bits in the group are counted, and, for odd parity, if the total number of bits is even, the parity bit is set to one, and the total number of bits transmitted adds up to an odd number (e.g., if the parity group is 101, the parity bit is set to one, and 1011 adds up to an odd number). If the total number of bits is odd, the parity bit is set to zero, and the total number of bits transmitted again forms an odd number (e.g., if the parity group is 100, the parity bit is set to zero, and 1000 adds up to an odd number). At the receiving end, each group of bits, along with the parity bit, is checked to see if the total number of bits adds up to an odd number, and, if so, transmission has occurred successfully. Alternatively, it is possible to use even parity, in which case the parity bit is set to one if the total number of bits is odd.
Redundant disk arrays, such as RAID devices Level 3 (RAID-3 devices) and RAID-5 devices, may be used to build highly available and reliable disk subsystems, which is described further in A. Patterson, G. A. Gibson, and R. Katz, “A case for redundant arrays of inexpensive disks,” in Proc. SIGMOD Int. Conf. Data Management, Chicago, Ill., 1988, pp. 109-116. Typically, the exclusive-OR (XOR) of data from some number of disks is maintained on a redundant disk, and, in the event of a disk failure, the data on the failed disk may be reconstructed by performing the XOR operation on the data on the surviving disks, and writing this into a spare disk. The ⊕ symbol represents an XOR operation. With a two input XOR operation, for any two inputs, if either input is True (i.e., 1) (but not both), then the output is True (i.e., 1).
However, data may be lost if the second disk fails before the reconstruction is complete. In, for example, Burkhard and J. Menon, “Disk Array System Storage Reliability”, International Symposium Fault-Tolerant Computing, pp. 432-441, 1993, it was shown that traditional disk arrays that can protect from the simultaneous loss of no more than one disk will prove to be inadequate by the year 2000.
Consequently, several techniques have been considered to design systems that will not lose data even when multiple disks fail simultaneously. These techniques are further described in, for example, I. Park, “Efficient placement of parity and data to tolerate two disk failures in disk array systems,” IEEE Trans. Parallel and Distributed Systems, vol. 6, no. 11, pp. 1177-1184, November 1995; Blaum, J. Brady, J. Bruck and J. Menon, “EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures,” IEEE Trans. Computers, vol. 44, no. 2, pp. 192-202, February 1995; Blaum, J. Brady, J. Bruck and J. Menon, “Methods and means for encoding and rebuilding data contents up to two unavailable DASDSs in a DASD array using simple non-recursive diagonal and row parity,” U.S. Pat. No. 5,579,475, issued November 1996; Blaum, H. Hao, R. Mattson and J. Menon, “Methods and means for encoding and rebuilding data contents up to two unavailable DASDSs in an array of DASDs,” U.S. Pat. No. 5,271,012, issued December 1993; Gibson, L. Hellerstein, R. M. Karp, R. H. Katz, and D. A. Patterson, “Coding techniques for handling failures in large disk arrays,” Report No. UCB/CSD 88/477, December 1988; and Edirisooriya, S “METHOD OF ENCODING DATA SIGNALS FOR STORAGE” U.S. Pat. No. 6,247,157, issued on Jun. 21, 2001.
RAID devices Level 6 (RAID-6 devices) are similar to RAID-5 but include a second parity scheme that is distributed across different drives. In particular, RAID-6 devices provide support for recovering from two disk failures by maintaining two sets of parity groups. These parity groups may be referred to as horizontal and diagonal parity. The parity groups are formed so that each data block is present in both parity groups. Consequently, when modifying a data block, it is necessary to update two parity blocks.
Notwithstanding existing techniques for resolving simultaneous multiple disk failures, there is a need in the art for improved parity computation.